As you might have guessed from the introduction, this volume is something of a C potpourri. George Matas (University of Surrey, U.K.) presents his "LL" for a generic double-linked list library with examples. Sverre H. Huseby (Oslo, Norway) contributes "GIFSave" to save bitmaps in this popular image file format. Last, "Cordic++" by Timothy M. Farnum (Rochester, NY) builds on Michael Bertrand's C implementation of fast trigonometric functions. Altogether, three very useful and specialized tools for common C problems. The entire set fits on just one diskette. This diskette is immediately available as CUG volume #401. [LL: CUG#401A] LL is a double-linked list handler library with more than four dozen operator functions. Variables of any type can be stored in an LL list. Individual elements of a list may be of different types. Any depth of lists of lists can be created. An instance of a list is created using either ConsLL(), ConsCopyLL() or ConsPtrLL() functions. Its best to call one of these functions at the point of declaration of a list variable. The result of one of the constructor functions must be assigned to a given list instance before passing it to any other function in the LL library. ConsLL() creates an empty list. ConsCopyLL(src) creates a new copy of an existing list. ConsPtrLL(src) creates a list of pointers to elements stored in list 'src'. DestLL(list) destroys a list, ie. deletes all elements and frees all memory allocated for 'list'. It should be called at the point where 'list' goes out of scope. LL has been tested only on SUN Sparcstations and DEC Ultrix machines. In these environments, it works with both the native "cc" compiler as well as GNU C ("gcc"). The CUG Library distribution includes source only. [GIFSave: CUG#401B] The GIFSAVE library makes it possible to save GIF-images from your own graphic-producing C-programs. GIFSAVE creates simple GIF-files following the GIF87a standard. Interlaced images can not be created, and there should only be one image per file. GIFSAVE has been released as Public Domain source code with no restrictions on its usage. GIFSAVE consists of four functions, all decleared in GIFSAVE.H: * GIF_Create() creates new GIF-files. It takes parameters specifying the filename, screen size, number of colors, and color resolution. * GIF_SetColor() sets up the red, green and blue color components. It should be called once for each possible color. * GIF_CompressImage() performs the compression of the image. It accepts parameters describing the position and size of the image on screen, and a user defined callback function that is supposed to fetch the pixel values. * GIF_Close() terminates and closes the file. The functions should be called in the listed order for each GIF-file. One file must be closed before a new one can be created. To use these functions, you must create a callback function that will do what is needed to get the pixel values for each point in the image. GIFSAVE includes a makefile for use with Borland C/C++. Huseby claims he has taken care to insure that all byte-order sensitive operations are handled in platform independent method. This means the source code should work without modification on non-MS-DOS platforms. The Graphics Interchange Format(c) is the Copyright property of CompuServe Incorporated. GIF(tm) is a Service Mark property of CompuServe Incorporated. [CORDIC++: CUG#401C] The Coordinate Rotational Digital Computer (CORDIC) was an early device implementing fast integer sine and cosine calculations. By favoring integer operations over floating point, it represents a classic computing tradeoff of speed vs. precision. Although first documented by Jack E. Volder in 1959, most CUG readers may remember Michael Bertrand's C implementation in CUG Vol. 10, No. 11 (November 1992). Farnum presents his own reimplementation of Bertrand's code this time as a full C++ class.
According to Farnum, the most notable change for C++ is encapsulating the variables which were global in the C version. As static member variables of "cordic" class they become protected from accidental modification by routines unaware of them. Moving these variables inside a class structure makes it necessary to develop interface routines, and also requires that a decision be made about how the class will be used. Farnum decided to predefine one member of the cordic class, "cord", to access the member functions which compute the integer sine and cosine. Other instances of class cordic can be created and will work as well as the predefined instance, but there is little advantage to this in the current implementation.
One implementation possibility left open to other readers is providing the ability to instantiate the class with different levels of accuracy. This would be done by using different bases for the CORDIC algorithm. Farnum decided against that alternative because the complexity of implementation and its use seemed to go against the straightforwardness which is the main advantage of the CORDIC algorithm.
The C++SIM discrete event process based simulation package provides Simula-style class libraries. C++SIM is a newly released package from M.C. Little and D. McCue at the Department of Computing Science in the University of Newcastle upon Tyne (England). The same distribution also includes the SIMSET linked list manipulation facilities. According to MacLennan (1983), Simula was the first computer language to incorporate the ideas of a "class" and "object" constructs in 1967. SIM++ currently claims usability only on Unix workstations, such as SUN Sparcs. C++SIM version 1.0 (released 06/15/92) is now available as CUG volume #394.
C++SIM uses inheritance throughout the design to an even greater extent than already provided by Simula. This allows adding mew functionality without affecting the overall system structure. Thus, inheritance provides for a more flexible and expandable simulation package. Specifically, C++SIM supports the following classes: Process, ProcessList, ProcessIterator, ProcessCons, Random, Element & Head, thread, lwp_thread, an gnu_thread.
C++SIM includes a paper describing its design and implementation and examples of how to use it. The paper describes the class hierarchy itself as well as how to further refine the simulation package.
The simulation package requires a threads package and currently only works with either the Sun lightweight process library or the included GNU thread package. The thread library is the only system-specific code, so porting the remainder to other Unix workstations should be easy. C++SIM compiles with Cfront 2.1 and Cfront 3.0.1 and GNU g++ 2.3.3
The C++SIM license grants permission to use, copy, modify and distribute the program for evaluation, teaching and/or research purposes only and without fee. The University of Newcastle upon Tyne copyright and permission notice must appear on all copies and supporting documentation, and similar conditions are imposed on any individual or organization to whom the program is distributed.
This volume combines three relatively small but powerful archives on a single diskette. Chris Thewalt (University of California at Berkeley, Civil Engineering) presents his interactive line editor library. Walter Karas (Cary, NC) contributes his implementation of the classic binary search tree with AVL balancing. Last, Christopher Sawtell (Linwood, Christchurch, New Zealand) releases his Typing Tutor for use with Curses. All three are immediately available as CUG volume #395.
Input-Edit, also known as getline, provides an easy method to greatly increase the functionality of programs which read input a line at a time. Interactive programs that read input line by line can now provide line editing and history functionality to the end-user that runs the program. As far as the programmer is concerned, the program only asks for the next line of input. However, until the user presses the [RETURN] key they can use emacs-style line editing commands and can traverse the history of lines previously typed.
Other packages, such as GNU's readline, have greater capability but are also substantially larger. Input-edit is small (1200 source lines) and quite portable because it uses neither stdio nor any termcap features. For example, it only uses \b to backspace and \007 to ring the bell on errors. Since it cannot edit multiple lines it scrolls long lines left and right on the same line.
Input edit uses K&R C and can run on any Unix system (BSD, SYSV or POSIX), AIX, XENIX, MS-DOS with MSC, Borland Turbo C, or djgpp, OS/2 with gcc (EMX), and DEC VAX-11 VMS. Porting the package to new systems consists mainly of maintaining the function to read a character when it is typed without echoing it.
SORTLIST implements a "sorted list" data structure library in ANSI C. This library is appropriate whenever all elements of the sorted list have the following characteristics:
Symbol tables and dictionary applications are excellent candidates for the sorted list data structure. This implementation of a sorted list data structure employs an AVL tree. AVL trees were invented by Adelson-Velskii and Landis in 1962. Specifically, Karas draws on algorithms presented by Horowitz and Sahni in "Fundamentals of Data Structures" (Computer Science Press). The add, find, and delete operations on an AVL tree have worst-case O(log n) time complexity. SORTLIST version 1.1 (released 8/25/93) is now available on CUG volume #395.
The Typing Tutor for use with Curses is a marvel of compactness. Since it builds on the substantial functionality of the Unix curses library, the Typing Tutor consists of just 250 source lines. The learning scenario is simple, yet easily customizable to fit any lesson plan. The screen is broken into two windows. The top window contains the "lesson" which is the text you will be typing from. The bottom window contains the results of your (presumably) touch typing. Everytime a character in the bottom window fails to match the original in the top window, it is flagged by changing the screen attribute to flashing. Although Sawtell does not specify compatability for Typing Tutor, he expects it to run on any Unix system with a curses package available.
NNUTILS, by Gregory Stevens (Rochester, NY), is a public domain package meant to help you to start programming neural networks in C. It is a tutorial about how to program neural networks where source code is your textbook. Stevens' intensely documented source code contains everything you need to implement several kinds of net architectures. NNUTILS gives you a series of simple implementations to let you see how they work step by step. NNUTILS version 1.01 (released 08/02/93) is immediately available as CUG #396.
Each subdirectory contains a different example with six standard C source files and a main program with a name similar to that of the directory. The source is written ANSI compliant C and developed primarily under Borland C++ 3.1. Accordingly, the CUG distribution includes DOS executables and project files for each implementation. Because the code is ANSI compliant, all of the examples work with GNU C under UNIX. Building executables with GNU C is simple enough that no makefiles are included.
Briefly, here's a summary of problem sets included with NNUTILS:
| NNTEST1 | A network with one input node and one output node. |
| NNTEST2 | A network using the "logistic" activation function (as opposed to linear). |
| NNXOR | A network implementation of the famous |
| NNSIM1 | A generic feed-forward network with backpropagation. |
| NNWHERE | A 5x5 retina is presented with shapes it must classify correctly. |
| NNWHAT | A continuation of above where shapes can assume any position. |
| NNEVOLVE | A feed-forward, back-propagation supervised net. |
| NNSIM2 | Simulates a competitive learning network with a Hebbian learning algorithm. |
| NNRECUR1 | A recurrent net with back-propagation, a kind of supervised learning called Self-Correlating, where the input patterns serve as their own output patterns. |
Landon Noll (Sunnyvale, CA) submits a decade of source code from the International Obfuscated C Code Contest (IOCCC). This contest has long been a favorite of many CUJ readers. The entire IOCCC archive from 1984-1993 is now available as a two diskette set from CUG Library. Obfuscation implies purposefully obscuring and confusing a situation. Why obfuscate C code? The official IOCCC rules state it succinctly:
Recently, Bob van der Poel reviewed Don Libes' book entitled Obfuscated C and Other Mysteries (see C Users Journal, Vol. 11, No. 10, October 1993, pp. 131-132). The diskette for this book includes IOCCC entries from 1984-1991. Libes has produced special reports about the IOCCC several times in the CUJ. Please see the following back issues for more detail:
Libes, Don. "Don't Put This on Your Resume'", C Users Journal, May 1991, p. 89.
Libes, Don. "The Far Side of C", C Users Journal, May 1990, p. 125.
Libes, Don. "The International Obfuscated C Code Contest", C Users Journal, July 1989, p. 93.
The CUG Library volume #397 contains the full IOCCC archive including two additional years not included in the Libes book.
In addition to dozens and dozens of obfuscated C programs, the archive includes complete rules and guidelines so you can submit your own entries into next years contest. Some of the obfuscated programs are quite useful, including scaled-down versions of make, grep, and editors.
Cross assemblers continue to play an important role in the CUG Library. A cross assembler reads assembly language source code for a non-native CPU and writes object code that can be linked and downloaded to the target machine for execution. Developers of embedded systems are the most frequent users of cross assemblers. This month, Alan R. Baldwin (Kent State University, Ohio), adds his third cross assembler to the CUG Library's repetoire. ASxxx Part 3 provides a complete Motorola 68HC08 development system. ASxxx Part 3 version 1.50 (released 8/9/93) is immediately available as CUG volume #398.
The CUG distribution of ASxxx Part 3 includes MS-DOS executables for the ASxxx Cross Assembler and Linker. However, if you want to recompile the Cross Assembler or Linker, you'll also need ASxxx Part 1 (CUG #292). ASxxx Part 2 contains cross assembler source files for the 6816 CPU. The ASxxxx family of cross assemblers can be built on DEC machines running DECUS C in the TSX+ environment or PDOS C v5.4b under RT-11. ASxxxx has been built with Borland C++ v3.1 under MS-DOS and includes a project (.PRJ) file. Although only these implementations have been specifically tested, Baldwin claims many other K&R C compilers may work as well.
ASxxx Part 3 includes a comprehensive 80-page manual covering functionality provided by all three existing ASxxxx cross assemblers and linkers. The documentation lays out the exact specifications of syntax for symbols, labels, assembler directives, and expressions in detail. The manual includes appendices with instruction set highlights and supported syntax for Motorola 6800, 6801, 6804, 6805, 68HC08, 6809, 6811 6816, Intel 8080 and 8085, and Zilog Z80 and HD64180 CPUs.
The ASxxxx assembler falls short of full macro implementation, but does include a host of important features such as: if/then/else, #include files, radix support from binary to hexadecimal, and a full complement of C-language operators for expressions. The ASxxxx linker goes beyond conventional loaders by resolving intermodule symbols, combining code into segments, relocating absolute symbols and base addresses, and producing either Intel HEX or Motorola S19 output files.
MINED, by Thomas Wolff (Freie Universität Berlin, Institut für Informatik, Germany), is a modeless full-screen text editor. MINED was originally written for MINIX and now works with most Unix platforms as well as MS-DOS, and DEC VAX-11/VMS. It works best at editing small files (50K or less) and can edit many files simultaneously. Unlike other editors which have separate command modes and input modes, MINED uses a modeless design for ease of use. It also includes a powerful regular expressions for both searching and replacing text. MINED Version 3 (released 08/04/93) is immediately available as CUG volume #399.
